package Offer.q115_sequenceReconstruction;

import java.util.*;

public class Solution {
    public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
        int n = nums.length;
        Set<Integer> set = new HashSet<>();
        for (int[] sequence : sequences) {
            for (int i : sequence) {
                set.add(i);
            }
        }
        if (set.size() != n) return false;

        int[] inDegree = new int[n + 1]; // 入度表 从1开始的 1到n 所以长度开大一个  以此对应下标
        List<List<Integer>> adjTable = new ArrayList<>();  // 邻接表
        for (int i = 0; i <= n; i++) adjTable.add(new ArrayList<>()); // 填充邻接表 记录每一个数字邻接的数字

        for (int[] sequence : sequences) {
            for (int i = 0; i < sequence.length - 1; i++) {
                int from = sequence[i], to = sequence[i + 1];
                adjTable.get(from).add(to);
                ++inDegree[to];
            }
        }

        // 前面的都属于是构建图的过程 接下来是遍历的过程
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i < inDegree.length; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }

        int[] res = new int[n];
        int count = 0;
        while (!queue.isEmpty()) {
            if (queue.size() > 1) return false;

            int cur = queue.poll();
            res[count] = cur;
            ++count;

            for (Integer to : adjTable.get(cur)) {
                --inDegree[to];
                if (inDegree[to] == 0) queue.offer(to);
            }
        }

        for (int i = 0; i < res.length; i++) {
            if (res[i] != nums[i]) return false;
        }

        return true;
    }
}
